AtCoder ABC 038 C - 単調増加 (100点)

https://gyazo.com/5d84931ceb06d02d0add0b7f19bc1818

考察履歴

code:疑似

for i in 0..N

for j in i..N

count += 1

else

break

当然TLEするのでNG

単調増加を見つけて、処理していくので尺取法でできそうと考えた

が、うまく数え上げる方法がわからず、断念

解説見ると、尺取法で考えるのがスタンダードなよう

別途学習する

数学を使って解くようなことを考えた

単調増加の要素数がわかれば、そこでの数え上げは数列の法則から導けるのではないかと考えた

単調増加の要素数

１個：１パターン

２個：３パターン

３個：６パターン

４個：１０パターン

ここらへんの導出は等差数列、階差数列の和の公式を使って行える

同じ数字が続く部分は単調増加ではないので、除外する必要がある

その後、単調増加を判定していく

これもansに追加する

以上でACできた。

が、尺取法での実装がスタンダード

尺取法での検討

本問題での「単調増加」という条件が、「条件を満たしている区間の部分区間も条件を満たす」構造をしているので尺取法が適用可能

res += right - left;　で数え上げていく

今回の問題で、尺取法がOKでは？と注意することはできた

次回また気になったら、もう少し深く検討するようにする

実装

C++で行ったが、いろいろ初歩的なところでつまずいた

code:cpp

code:cpp

vector<std::pair<ll, ll>> rle = rle(a); //変数名をrleにするとエラー

pointer-to-function 型に対する適切な operator() または変換関数のないクラス型のオブジェクトの呼び出しです

とエラー。変数名をa_rleなどに変えるとOK。別の変数ではなく関数ポインタと認識されるのか？詳細あまり理解できていないが、エラーとのこと。

ACコード

code:cpp

using namespace std;

typedef long long ll;

vector<std::pair<ll, ll>> rle(const vector<ll> v){

vector<std::pair<ll, ll>> res;

ll pre = -1;

ll chain = 1;

for(auto iter = begin(v); iter != end(v); ++iter){

if(*iter == pre){

chain += 1;

}else{

if(pre != -1){

res.push_back(make_pair(pre,chain));

}

pre = *iter;

chain = 1;

}

}

res.push_back(make_pair(pre, chain));

return res;

}

int main(){

ll n; cin >> n;

vector<std::pair<ll, ll>> a_rle = rle(a); //変数名をrleにするとエラー

vector<ll> increase;

ll count = 1;

for(auto i = 1; i < a_rle.size(); ++i){

count += 1;

}else{

increase.push_back(count);

count = 1;

}

}

increase.push_back(count);

ll ans = 0;

for(auto iter = begin(increase); iter != end(increase); ++iter){

ans += 1 + ((*iter-1) * (*iter+2)) / 2;

}

ans += n - a_rle.size();

cout << ans << endl;

}